package com.algorithm;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author: sun.hongliang
 * @create: 2019/09/21 11:31
 */
public class MaxDepthTest {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int max_left = maxDepth(root.left);
        int max_right = maxDepth(root.right);
        return Math.max(max_left, max_right) + 1;
    }


    public int maxDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<Record> queue = new LinkedList<>();
        queue.add(new Record(root, 1));
        int depth = 0;
        while (!queue.isEmpty()) {
            Record poll = queue.poll();
            TreeNode treeNode = poll.getTreeNode();
            depth = Math.max(poll.getDepth(), depth);
            if (treeNode.left != null) {
                queue.add(new Record(treeNode.left, poll.getDepth() + 1));
            }
            if (treeNode.right != null) {
                queue.add(new Record(treeNode.right, poll.getDepth() + 1));
            }
        }
        return depth;
    }

    class Record {
        private TreeNode treeNode;
        private int depth;

        public Record(TreeNode treeNode, int depth) {
            this.treeNode = treeNode;
            this.depth = depth;
        }

        public TreeNode getTreeNode() {
            return treeNode;
        }

        public void setTreeNode(TreeNode treeNode) {
            this.treeNode = treeNode;
        }

        public int getDepth() {
            return depth;
        }

        public void setDepth(int depth) {
            this.depth = depth;
        }
    }

}
